require 'sudoku'
require 'cell'
require 'invalid_sudoku_error'

class SudokuSolver

  POSSIBLE_VALUES = 'possible_values' # value is a set of ints
  SELECTED_VALUE  = 'selected_value' # currently selected, an int
  BRANCH_POINT    = 'branch_point' # value is a cell
  PREVIOUS        = 'previous' # reference to the previous snapshot
  def initialize
    @i=0
  end  

  def getNext(sudoku)

    @i=@i+1


    n = sudoku.clone


    n.properties[PREVIOUS]=sudoku
    unsolvedCells = n.unsolvedCells

    #puts "step #{@i} - no of unresolved cells is #{unsolvedCells.length}"
    
    for cell in n.unsolvedCells do
      cell.properties[POSSIBLE_VALUES] = sudoku.possibleValues(cell.column,cell.row)
    end

    cell = selectCell(n);

    if n==nil
      puts 'sudoku solved!'
    else
      values = cell.properties[POSSIBLE_VALUES]
      if values.length==1
        # next cell solved
        #puts 'cell #{cell.inspect} solved, setting value to #{values[0]}'
        cell.value = values[0]
        return n
      elsif values.length==0
        #backtrack
        branchpoint = findBranchPoint(sudoku)
        activeCell = branchpoint.properties[BRANCH_POINT]
        possibleValues = activeCell.properties[POSSIBLE_VALUES]
        activeCell.value = possibleValues.pop
        #puts 'backtrack and start new branch at ' + activeCell.inspect
        return branchpoint
      else
        # start branching
        cell.value = values.pop
        n.properties[BRANCH_POINT]=cell
        #puts 'start branching at cell ' + cell.inspect
				return n
      end
    end


#		else {
#			Collection<Integer> values = (Collection<Integer>) cell.getProperty(POSSIBLE_VALUES);
#			if (values.size()==0) {
#				// need to backtrack
#				Snapshot branchPoint = findBranchpoint(current);
#				Cell activeCell = (Cell)branchPoint.getProperty(BRANCH_POINT);
#				Collection<Integer> possibleValues = (Collection<Integer>) activeCell.getProperty(POSSIBLE_VALUES);
#				int v = possibleValues.iterator().next();
#				activeCell.setValue(v);
#				possibleValues.remove(v);
#				System.out.println("backtrack and start new branch at " + activeCell);
#				return branchPoint;
#			}
#			else if (values.size()==1) {
#				// next solution found
#				int v = values.iterator().next();
#				cell.setValue(v);
#				System.out.println("step, set new value to cell " + cell);
#				return next;
#			}
#			else {
#				// start branching
#				int v = values.iterator().next();
#				cell.setValue(v);
#				values.remove(v);
#				next.setProperty(BRANCH_POINT,cell);
#				System.out.println("start branching at cell " + cell);
#				return next;
#			}
#		}

  end

  def checkConsistency(sudoku)
      checkCOnsistency(sudoku.cells,'all')
  end


  def isComplete(sudoku)
    for cell in sudoku.cells do
      if cell.value==0
        false
      end
    end
    true
  end

  private
  def selectCell(sudoku)
    best_cell = nil
    best_value = 10
    for cell in sudoku.unsolvedCells do
      s = cell.properties[POSSIBLE_VALUES].length
      if s < best_value
        best_cell = cell
        best_value = s
      end
    end
    best_cell
  end

  def findBranchPoint(sudoku)
    previous = sudoku.properties[PREVIOUS]
    if previous!=nil
      cell = previous.properties[BRANCH_POINT]
      if (cell==nil)
        findBranchPoint(previous)
      else
        possibleValues = cell.properties[POSSIBLE_VALUES]
        if possibleValues.length>0
          previous
        else
          findBranchPoint(previous)
        end
      end
    else
      puts 'no branchpoint found'
    end

  end

  def checkConsistency(cells,groupName)
    expected = 1..9
    actual = cells.collect{|c|c.value}
    if (expected & actual).length<9
      raise InvalidSudokuError.exception("inconsitent sudoku exception in #{groupName}")
    end
  end


end